package com.wk.arth.od;

import java.util.Arrays;

/**
 * 并查集
 * 根节点保存值为节点数量的负值
 * 其他节点值为上级的索引
 * 权重
 * 压缩路径
 * @author wukai
 * @date 2023/4/25 13:20
 */
public class UnionFindSet {
    public int[] elem;
    public UnionFindSet(int n){
        elem = new int[n];
        Arrays.fill(elem,-1);
    }
    public int findRoot(int x){
        if(x<0){
            throw new IllegalArgumentException("下标不能是负数");
        }
//        while(elem[x]>=0){
//            x = elem[x];
//        }
//        return x;
        if(elem[x]<0){
            return x;
        }
        return (elem[x]=findRoot(elem[x]));
    }
    public boolean isConnect(int x1,int x2){
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        return index1 == index2;
    }
    public void union(int x1,int x2){
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if(index1 == index2){
            System.out.println("已经联通");
            return;
        }
        elem[index1] = elem[index1]+elem[index2];
        elem[index2] = index1;
    }
    // 未联通集合数量
    public int getCount(){
        int count = 0;
        for(int x:elem){
            if(x<0){
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        UnionFindSet set = new UnionFindSet(10);
        set.union(0,6);
        set.union(6,7);
        set.union(7,8);
        set.union(1,4);
        set.union(1,9);
        set.union(2,3);
        set.union(2,5);
        System.out.println(set.getCount());
        System.out.println(set.isConnect(0,8));
        System.out.println(set.isConnect(1,2));
    }
}
